package dp.practice5;

public class Main2 {
    public static void main(String[] args) {
        System.out.println(minimumComb(15));
        System.out.println(minimumComb(100));
    }

    /**
     * DP方法
     *
     * @param w 钱数
     * @return 最小面值组合的数量
     */
    private static int minimumComb(int w) {
        int[] count = new int[w + 1];
        for (int i = 1; i <= w; i++) {
            int cost = Integer.MAX_VALUE;
            if (i - 1 >= 0) cost = Math.min(cost, count[i - 1] + 1);
            if (i - 5 >= 0) cost = Math.min(cost, count[i - 5] + 1);
            if (i - 11 >= 0) cost = Math.min(cost, count[i - 11] + 1);
            count[i] = cost;
            System.out.printf("count[%d]=%d\n", i, count[i]);
        }
        return count[w];
    }
}
